import java.util.Arrays;

public class MyHeap {
    int[] elme;
    int useSize;
    public MyHeap() {
        this.elme = new int[10];
    }
    public void Array(int[] array){
        for (int i=0;i<array.length;i++){
            elme[i]=array[i];
            useSize++;
        }
    }
    //创建大根堆
    public void createHeap(){
    for (int i=(useSize-1)/2;i>=0;i--){
        siftDown(i,useSize);
    }
    }
    //向下调整
    private void siftDown(int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if(child+1<len&&elme[child]<elme[child+1]){
                child=child+1;
            }
            if (child>parent){
                swap(parent,child);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //交换
    public void swap(int i,int j){
        int tmp=elme[i];
        elme[i]=elme[j];
        elme[j]=tmp;
    }

    //增加元素
    public void push(int val){
        //如果满了、扩容
        if(useSize==elme.length){
            elme= Arrays.copyOf(elme,2*elme.length);
        }
        elme[useSize]=val;
        siftup(useSize);
        useSize++;
    }
    private void siftup(int child){
        int parent=(child-1)/2;
        while (child>0){
            if (elme[child]>elme[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {break;}
        }

    }
    public int pop(){
        if(useSize==0){
            return -1;
        }
        int r=elme[0];
        useSize--;
        swap(0,useSize);
        siftDown(0,useSize);
        return elme[0];
    }

}
